495. [20181013] {naagi}

Кирпичный червь Эдгар живёт в плоской кирпичной стене.
Стена бесконечна во все стороны.
Каждый кирпич состоит из двух соседних клеток плоскости:
для чётных полос в одном и том же кирпиче находятся клетки
$(2 i, 2 j)$ и $(2 i + 1, 2 j)$, а для нечётных полос "--- клетки
$(2 i - 1, 2 j + 1)$ и $(2 i, 2 j + 1)$.

Червь хочет из середины одной клетки попасть в середину другой клетки.
Но он не любит проходить сквозь цемент между кирпичами:
если нужно перебраться из какого-то кирпича в соседний,
червь движется перпендикулярно их общей границе.
Какое наименьшее количество раз ему всё же придётся пройти сквозь цемент?
